import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

public class Offer37 {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "[]";
        }
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        while (!deque.isEmpty()){
            TreeNode pop = deque.removeFirst();
            if (pop!=null){
                stringBuilder.append(pop.val).append(",");
                deque.add(pop.left);
                deque.add(pop.right);
            }else {
                stringBuilder.append("null").append(",");
            }
        }
        stringBuilder.deleteCharAt(stringBuilder.length()-1);
        stringBuilder.append("]");
        return stringBuilder.toString();
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data==null||data.equals("[]")) return null;
        String[] split = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(split[0]));
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        int i =1;
        while (!deque.isEmpty()){
            TreeNode treeNode = deque.removeFirst();
            if (!split[i].equals("null")){
                treeNode.left=new TreeNode(Integer.parseInt(split[i]));
                deque.add(treeNode.left);
            }
            i++;
            if (!split[i].equals("null")){
                treeNode.right=new TreeNode(Integer.parseInt(split[i]));
                deque.add(treeNode.right);
            }
            i++;
        }
        return root;
    }
}
